CODE 56. Combinations

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/03/2013-10-03-CODE 56 Combinations/

访问原文「CODE 56. Combinations」

Given two integers n and k, return all possible combinations ofk numbers out of 1 … n.For example,
Ifn= 4 andk= 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (n < k) {
		return null;
	}
	
	ArrayList<Integer> sList = new ArrayList<Integer>();
	for (int i = 1; i <= n; i++) {
		sList.add(i);
	}
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	for (int i = 1; i <= n; i++) {
		ArrayList<Integer> element = new ArrayList<Integer>();
		element.add(i);
		result.add(element);
	}
	int start = 0;
	int end = result.size();
	for (int num = 2; num <= k; num++) {
		ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();
		for (int i = start; i < end; i++) {
			ArrayList<Integer> oldElement = result.get(i);
			for (int j = sList
					.indexOf(oldElement.get(oldElement.size() - 1)) + 2; j <= n; j++) {
				ArrayList<Integer> element = new ArrayList<Integer>();
				element.addAll(oldElement);
				element.add(j);
				tmp.add(element);
			}
		}
		result.clear();
		result.addAll(tmp);
		start = 0;
		end = result.size();
	}
	return result;
}